package algorithm.Sort;

import java.util.Arrays;

/**
 * 有序数组背景下 二分搜索可以适用于三种情况
 * 1. 验证一个有序数组中是否存在一个数num
 * 2. 寻找>=num的最左位置
 * 3. 寻找<=num的最右位置
 */
public class BinarySort {

    /**
     * 普通的二分查找，查找num是否存在于当前数组中
     * @param array
     * @param num
     * @return
     */
    public static boolean binarySortFindNum(int[] array,int num){
        Arrays.sort(array);
        if(array.length==0) return false;
        int l=0,r=array.length-1,m=0;
        while(l<=r){
            m=(l+r)/2;
            if(array[m]>num){
                r=m-1;
            }else if(array[m]<num){
                l=m+1;
            }else{
                return true;
            }
        }
        return false;
    }

    /**
     * 找到返回下标，找不到返回-1
     * @param array
     * @param num
     * @return
     */
    public static int binarySortFindMostLeft(int[] array,int num){
        Arrays.sort(array);
        int ans=-1;
        if(array.length==0) return -1;
        int l=0,r=array.length-1,m=0;
        while(l<=r){
            m=(l+r)/2;
            if(array[m]>=num){
                r=m-1;
                ans=m;
            }else{
                l=m+1;
            }
        }
        return ans;
    }

    /**
     * 找到返回下标，找不到返回-1
     * @param array
     * @param num
     * @return
     */
    public static int binarySortFindMostRight(int[] array,int num){
        Arrays.sort(array);
        int ans=-1;
        if(array.length==0) return -1;
        int l=0,r=array.length-1,m=0;
        while(l<=r){
            m=(l+r)/2;
            if(array[m]>num){
                r=m-1;
            }else{
                l=m+1;
                ans=m;
            }
        }
        return ans;
    }

}
